import java.util.HashMap;
import java.util.Map;
// https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
public class BuildTree {
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val)
        {
            this.val = val;
        }
    }
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {

            HashMap<Integer,Integer> inOrderMap = new HashMap<>();
            for(int i = 0 ; i < inorder.length ; i++)
            {
                inOrderMap.put(inorder[i],i);
            }
            TreeNode node = buildTree(inorder,postorder,0,inorder.length -1, 0 , postorder.length-1,inOrderMap);
            return node;
        }
        private TreeNode buildTree(int [] inorder, int [] postorder , int inleft, int inright, int poleft , int poright , Map<Integer,Integer> inOrderMap)
        {

            if(inleft > inright) return null;
            TreeNode root = new TreeNode(postorder[poright]);
            int index = inOrderMap.get(root.val);
            root.left = buildTree(inorder,postorder,inleft,index-1,poleft, poleft + (index-inleft-1),inOrderMap);
            root.right = buildTree(inorder,postorder,index+1,inright,poleft + (index - inleft),poright-1,inOrderMap);
            return root;
        }


    }

}
